Fibonacci heap

斐波那契堆（Fibonacci heap）是電腦科學中樹的集合。它比二項式堆積具有更好的平攤分析效能，可用於實現合併優先佇列。不涉及刪除元素的操作有O(1)的平攤時間。 Extract-Min和Delete的數目和其它相比，較小時效率更佳。稠密圖每次decrease key只要O(1)的平攤時間，和二項式堆積的O(lg n)相比是巨大的改進。
-- https://zh.wikipedia.org/wiki/斐波那契堆

Fibonacci heap 有兩個主要目的：

1. 支持構成所謂的「可合併堆」的操作。
2. 幾個 Fibonacci 堆操作以固定的時間平攤運行，使得它非常適合用在需要經常調用這些操作的應用程序。

Mergeable heaps

Mergrable heap 有以下五個操作：

1. MAKE-HEAP () creates and returns a new heap containing no elements.
2. INSERT (H, x) inserts element x, whose key has already been filled in, into heap H .
3. MINIMUM (H) returns a pointer to the element in heap H whose key is minimum.
4. EXTRACT-MIN (H) deletes the element from heap H whose key is minimum, returning a pointer to the element.
5. UNION (H1, H 2) creates and returns a new heap that contains all the elements of heaps H1 and H2 . Heaps H1 and H2 are destroyed by this operation.
6. DECREASE-KEY (H, x, k) assigns to element x within heap H the new key value k, which we assume to be no greater than its current key value.
7. DELETE (H, x) deletes element x from heap H.

結構

1. 斐波那契堆積是由一組最小堆積有序樹構成的。每個節點的度數為其子節點的數目。樹的度數為其根節點的度數。
2. 有根的但是無序
3. 所有樹的根節點也用一個雙向迴圈連結串列連結起來
4. 使用一個指標指向斐波那契堆積中最小元素
   
   A 圖中，虛線連接的是根的列表，而 B 圖則標示了上下左右指針

插入

圖 A 至 圖 B 展示如何將 node 21 插入，以下為虛擬碼：

FIB-HEAP=INSERT(H, x)
    x.degree = 0
    x.p = NIL
    x.child = NIL
    x.mark == False
    if H.min == NIL
        create a root list for H containing just x
        H.min = x
   else insert x intp H's root list
       if x.key < H.min.key
           H.min = x
   H.n = H.n + 1

先產生須插入的節點，把新建的節點插入到根鏈表中，如果是最小值，則標記為堆的最小節點。插入位置沒有規定，一般插入到 min 的左邊。並把堆的「所有節點樹」值加 1